/*
题目: 最短的桥
给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。

岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。

你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。

返回必须翻转的 0 的最小数目。

https://leetcode.cn/problems/shortest-bridge
 */
public class ShortestBridge {
    int[] dir = new int[] {0, -1, 0, 1, 0};
    int n ;

    public int shortestBridge(int[][] grid) {
        n = grid.length;

        Queue<int[]> expand = new LinkedList<> ();
        boolean end = false;  // 用于直接结束两层循环
        for (int i = 0; i < n && !end; i ++) {
            for (int j = 0; j < n; j ++) {
                if (grid[i][j] == 1) { // 只标记一个岛
                    // 直接原地把这个岛标记为 2
                    dfs(grid, i, j, 2, expand);
                    end = true;
                    break;
                }
            }
        }

        int count = 0;
        while (! expand.isEmpty()) {
            int size = expand.size();
            while (size -- > 0) {
                int[] p = expand.poll();
                // 开始扩展岛 2
                for (int i = 0; i < 4; i ++) {
                    int nextX = p[0] + dir[i];
                    int nextY = p[1] + dir[i + 1];
                    // 越界或者本来就是 2 号岛
                    if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n || grid[nextX][nextY] == 2)
                        continue ;

                    if (grid[nextX][nextY] == 1)    return count ;
                    grid[nextX][nextY] = 2;
                    expand.offer(new int[] {nextX, nextY});
                }
            }

            count ++;
        }

        return count ;
    }

    private void dfs(int[][] grid, int x, int y, int mark, Queue<int[]> expand) {
        grid[x][y] = mark;
        expand.offer(new int[] {x, y});
        for (int i = 0; i < 4; i ++) {
            int nextX = x + dir[i];
            int nextY = y + dir[i + 1];
            if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n || grid[nextX][nextY] != 1)
                continue ;

            dfs(grid, nextX, nextY, mark, expand);
        }
    }
}
